m = 16
n = 8
k = 4

def i_j_sum(i,j):
    sum=0
    while i>0:
      sum+=int(i%10)
      i /= 10
    while j>0:
      sum+=int(j%10)
      j /= 10
    return sum

direction=[-1,0,1,0,-1]
def movingCount(m: int, n: int, k: int) -> int:
    queue=[(0,0)]
    grid=[[0 for _ in range(n)] for _ in range(m)]
    grid[0][0] = 1
    res=1
    while len(queue)>0:
        queueLen=len(queue)
        while queueLen>0:
            x,y=queue.pop(0)
            for s in range(4):
                i,j=x+direction[s],y+direction[s+1]
                if i>=0 and i<m and j>=0 and j<n:
                    if grid[i][j]==0 and i_j_sum(i,j)<=k:
                        res+=1
                        grid[i][j]=1
                        queue.append((i,j))
            queueLen-=1
    print(res)
movingCount(m,n,k)



